/******************************************************************************

	COPYRIGHT(C) JONAS 'SORTIE' TERMANSEN 2010.

	This file is part of the Maxsi Library.

	Maxsi Library is free software: you can redistribute it and/or modify it
	under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or (at your
	option) any later version.

	Maxsi Library is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
	License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with Maxsi Library. If not, see <http://www.gnu.org/licenses/>.

	Maxsi Library
	A powerful Cross-Platform C++ General Purpose Library that allows you to
	efficiently create high-performance and reliable applications.

	MaxsiSort.cpp
	Useful sorting functions.

******************************************************************************/

#include "MaxsiLibrary.h"

BeginMaxsiNamespace

//=============================================================================
//	Sort an unsorted string list without regard to case - System Locale.
//=============================================================================

void SortStringListISelection(char** StringList, size_t NumStrings)
{
	for ( size_t NumSorted = 0; NumSorted < (NumStrings-1); NumSorted++ )
	{
		size_t Least = NumSorted;

		for ( size_t I = NumSorted; I < NumStrings; I++ )
		{
			if ( strcasecmp(StringList[I], StringList[Least]) < 0 ) { Least = I; }
		}

		char* Temp = StringList[NumSorted];

		StringList[NumSorted] = StringList[Least];

		StringList[Least] = Temp;
	}
}

void SortStringListIInsertion(char** StringList, size_t NumStrings)
{
	size_t ProperLocation;

	for ( size_t NumSorted = 0; NumSorted < NumStrings; NumSorted++ )
	{
		for ( ProperLocation = 0; ProperLocation < NumSorted && strcasecmp(StringList[ProperLocation], StringList[NumSorted]) < 0; ProperLocation++ ) { }

		char* Sortee = StringList[NumSorted];

		for ( size_t N = NumSorted; N > ProperLocation; N-- ) { StringList[N] = StringList[N-1]; }

		StringList[ProperLocation] = Sortee;
	}
}

// Runs in T time, where O(log2(N) * N - log2(N)) < T < O(log2(N) * N)
void SortStringListIMerge(char** StringList, size_t NumStrings)
{
	size_t NumStringsRoundedUp = 1;

	while ( NumStringsRoundedUp < NumStrings ) { NumStringsRoundedUp *= 2; }

	for ( size_t RoundSize = 2; RoundSize <= NumStringsRoundedUp; RoundSize *= 2 )
	{ 
		size_t NumStacks = DivUp(NumStrings, RoundSize);

		for ( size_t I = 0; I < NumStacks; I++ )
		{
			size_t Left = NumStrings - RoundSize * I;
			size_t StackSize = (Left > RoundSize) ? RoundSize : Left;
			size_t Stack1 = I * RoundSize + 0;
			size_t Stack2 = I * RoundSize + RoundSize / 2;

			for ( size_t N = 0; N < (StackSize-1) && Stack1 < Stack2 && Stack2-I*RoundSize < StackSize; N++ )
			{	
				size_t Smallest;

				if ( strcasecmp(StringList[Stack1], StringList[Stack2]) < 0 )
				{
					Smallest = Stack1;
					Stack1++;
				}
				else
				{
					Smallest = Stack2;
					Stack1++;
					Stack2++;
				}

				char* Sortee = StringList[Smallest];

				for ( size_t M = Smallest; M > I * RoundSize + N; M-- )
				{
					StringList[M] = StringList[M-1];

				}

				StringList[I * RoundSize + N] = Sortee;
			}
		}
	}
}

//=============================================================================
//	Sort an unsorted string list without regard to case - Wide Characters.
//=============================================================================

void SortStringListISelection(wchar_t** StringList, size_t NumStrings)
{
	for ( size_t NumSorted = 0; NumSorted < (NumStrings-1); NumSorted++ )
	{
		size_t Least = NumSorted;

		for ( size_t I = NumSorted; I < NumStrings; I++ )
		{
			if ( wcscasecmp(StringList[I], StringList[Least]) < 0 ) { Least = I; }
		}

		wchar_t* Temp = StringList[NumSorted];

		StringList[NumSorted] = StringList[Least];

		StringList[Least] = Temp;
	}
}

void SortStringListIInsertion(wchar_t** StringList, size_t NumStrings)
{
	size_t ProperLocation;

	for ( size_t NumSorted = 0; NumSorted < NumStrings; NumSorted++ )
	{
		for ( ProperLocation = 0; ProperLocation < NumSorted && wcscasecmp(StringList[ProperLocation], StringList[NumSorted]) < 0; ProperLocation++ ) { }

		wchar_t* Sortee = StringList[NumSorted];

		for ( size_t N = NumSorted; N > ProperLocation; N-- ) { StringList[N] = StringList[N-1]; }

		StringList[ProperLocation] = Sortee;
	}
}

// Runs in T time, where O(log2(N) * N - log2(N)) < T < O(log2(N) * N)
void SortStringListIMerge(wchar_t** StringList, size_t NumStrings)
{
	size_t NumStringsRoundedUp = 1;

	while ( NumStringsRoundedUp < NumStrings ) { NumStringsRoundedUp *= 2; }

	for ( size_t RoundSize = 2; RoundSize <= NumStringsRoundedUp; RoundSize *= 2 )
	{ 
		size_t NumStacks = DivUp(NumStrings, RoundSize);

		for ( size_t I = 0; I < NumStacks; I++ )
		{
			size_t Left = NumStrings - RoundSize * I;
			size_t StackSize = (Left > RoundSize) ? RoundSize : Left;
			size_t Stack1 = I * RoundSize + 0;
			size_t Stack2 = I * RoundSize + RoundSize / 2;

			for ( size_t N = 0; N < (StackSize-1) && Stack1 < Stack2 && Stack2-I*RoundSize < StackSize; N++ )
			{	
				size_t Smallest;

				if ( wcscasecmp(StringList[Stack1], StringList[Stack2]) < 0 )
				{
					Smallest = Stack1;
					Stack1++;
				}
				else
				{
					Smallest = Stack2;
					Stack1++;
					Stack2++;
				}

				wchar_t* Sortee = StringList[Smallest];

				for ( size_t M = Smallest; M > I * RoundSize + N; M-- )
				{
					StringList[M] = StringList[M-1];

				}

				StringList[I * RoundSize + N] = Sortee;
			}
		}
	}
}

//=============================================================================
//	Add a string to a sorted string list - System Locale.
//=============================================================================

size_t AddStringToSortedStringListHalves(char** StringList, size_t N)
{
	if ( N == 1 ) { return 0; }

	size_t	NewEntry	=	N-1;
	size_t	LowerBound	=	0;
	size_t	UpperBound	=	N-2;
	size_t	Guess		=	LowerBound + (UpperBound - LowerBound)/2;
	int		Comparison;

	while ( true )
	{
		Comparison		=	strcasecmp(StringList[NewEntry], StringList[Guess]);

		if ( Comparison < 0 )
		{
			if ( Guess == LowerBound ) { break;}
			else { UpperBound = Guess - 1; Guess = LowerBound + (UpperBound - LowerBound)/2; }
		}
		else
		{
			if ( Guess == UpperBound ) { break; }
			else { LowerBound = Guess + 1; Guess = LowerBound + (UpperBound - LowerBound + 1)/2; }			
		}
	}

	char* Temp = StringList[NewEntry];

	UpperBound	=	NewEntry;
	LowerBound	=	Guess+1;

	if ( Comparison > 0 )
	{
		NewEntry		=	Guess+1;
	}
	else
	{
		NewEntry		=	Guess;
	}

	for ( size_t I = UpperBound; (I+1) > LowerBound; I-- )
	{
		StringList[I]	=	StringList[I-1];
	}

	StringList[NewEntry]	=	Temp;

	return NewEntry;
}

size_t AddStringToSortedStringListProbabillityGuess(char** StringList, size_t N)
{
	if ( N == 1 ) { return 0; }

	//size_t	NetEntryLen	=	strlen(StringList[N-1]);
	size_t	NewEntryNum	=	N-1;
	char*	NewEntry	=	StringList[NewEntryNum];
	size_t	LowerBound	=	0;
	size_t	UpperBound	=	N-2;
	int		Comparison;

	size_t	Value		=	*((uint8_t*)NewEntry[0]);

	size_t	Guess		=	Value * ((UpperBound - LowerBound) / 128);

	while ( true )
	{
		Comparison		=	strcmp(NewEntry, StringList[Guess]);

		if ( Comparison < 0 )
		{
			if ( Guess == LowerBound ) { break;}
			else { UpperBound = Guess - 1; Guess = LowerBound + (UpperBound - LowerBound)/2; }
		}
		else
		{
			if ( Guess == UpperBound ) { break; }
			else { LowerBound = Guess + 1; Guess = LowerBound + (UpperBound - LowerBound + 1)/2; }			
		}
	}

	UpperBound	=	NewEntryNum;
	LowerBound	=	Guess+1;

	if ( Comparison > 0 )
	{
		NewEntryNum		=	Guess+1;
	}
	else
	{
		NewEntryNum		=	Guess;
	}

	for ( size_t I = UpperBound; (I+1) > LowerBound; I-- )
	{
		StringList[I]	=	StringList[I-1];
	}

	StringList[NewEntryNum]	=	NewEntry;

	return NewEntryNum;
}

// StringList is a pointer to an array of already sorted strings, where the last
// entry is not sorted. This function will then find the proper place for the
// last entry to be, and then move the array around, so it will be in its proper
// place. The offset where the string ended up is returned.
size_t AddStringToSortedStringListIncludedStrCmp(char** StringList, size_t N)
{
	if ( N == 1 ) { return 0; }

	size_t	NewEntryNum	=	N-1;
	char*	NewEntry	=	StringList[NewEntryNum];

	size_t	NewEntryLen	=	0;

	// Find the length of NewEntry.
	while ( NewEntry[NewEntryLen] != 0 ) { NewEntryLen++; }

	size_t	LowerBound	=	0;
	size_t	UpperBound	=	N-2;
	int		Comparison	=	-1;

	size_t	Value		=	*((uint8_t*)NewEntry[0]);

	// Depending on the first char in NewEntry, make a statistic guess on the
	// location of NewEntry in the string list.
	size_t	GuessNum	=	Value * ((UpperBound - LowerBound) / 128);

	size_t	EqualChars	=	0;

	// Run the algorithm that finds where in the string list NewEntry belongs.
	// When finished, if Comparison > 0 then GuessNum+1 is the location of
	// NewEntry, otherwise GuessNum is the location of NewEntry.
	while ( true )
	{
		char*	Guess		=	StringList[GuessNum];

		// Compare NewEntry to Guess.
		// Comparison = strcmp(NewEntry, Guess)
		// Comparison is 0 if NewEntry or Guess is equal.
		// Comparison is -1 if NewEntry is less than Guess.
		// Comparison is 1 if NewEntry is greater than Guess.
		// If it has been determined that LowerBound and UpperBound both
		// shares the first EqualChars chars, then the first EqualChars
		// chars are skipped in the comparison. This makes the comparison
		// much cheaper for strings that are more alike, speeding up the
		// algorithm greatly.
		{
			Comparison		=	0;

			for ( size_t I = EqualChars; I < NewEntryLen; I++ )
			{
				if ( NewEntry[I] < Guess[I] ) { Comparison = -1; break; }
				if ( NewEntry[I] > Guess[I] ) { Comparison = 1; break; }
			}

			if ( Comparison == 0 && Guess[NewEntryLen] != 0 ) { Comparison = -1; }
		}

		// Depending on the result from the comparison, calculate the new
		// bounds and come up with a new rough guess of the location for
		// NewEntry.
		if ( Comparison < 0 )
		{
			if ( GuessNum == LowerBound ) { break;}
			else { UpperBound = GuessNum - 1; GuessNum = LowerBound + (UpperBound - LowerBound)/2; }
		}
		else
		{
			if ( GuessNum == UpperBound ) { break; }
			else { LowerBound = GuessNum + 1; GuessNum = LowerBound + (UpperBound - LowerBound + 1)/2; }			
		}

		// Calculate how many characters are shared by LowerBound and
		// UpperBound so that we can safely skip them next time we compare.
		while ( StringList[LowerBound][EqualChars] != 0 && StringList[LowerBound][EqualChars] == StringList[UpperBound][EqualChars] ) { EqualChars++; }
	}

	// Now move all the other entries to make room for NewEntry. This doesn't scale well. O(N)
	MAXSI_TODO("Add the Library Sort algorithm here!");
	UpperBound	=	NewEntryNum;
	LowerBound	=	GuessNum+1;

	if ( Comparison > 0 )
	{
		NewEntryNum		=	GuessNum+1;
	}
	else
	{
		NewEntryNum		=	GuessNum;
	}

	// Do the moving
	for ( size_t I = UpperBound; (I+1) > LowerBound; I-- )
	{
		StringList[I]	=	StringList[I-1];
	}

	// Now put NewEntry where it belongs.
	StringList[NewEntryNum]	=	NewEntry;

	return NewEntryNum;
}

EndMaxsiNamespace

